/*
 * lcstr.c
 *
 *  Created on: Dec 1, 2010
 *      Author: cumeo89
 */

#include "lcstr.h"
#include "suffixtree.h"
#include "util.h"
#include <glib.h>

gboolean countStringIndex(Node *node, int index) {
	if (n_isLeaf(node)) {
		return node->parentEdge->stringIndex == index;
	}
	gboolean found = FALSE;
	g_slist_foreach(iter, node->edges) {
		Edge *edge = iter->data;
		if (countStringIndex(edge->child, index)) {
			found = TRUE;
		}
	}
	if (found) {
		node->_c++;
	}
	return found;
}

void findExactLongest(Node *node, CommonString *cs, const gchar **strings, int depth) {
	if (node->_c > 1 && cs[node->_c-2].length < depth) {
		cs[node->_c-2].length = depth;
		cs[node->_c-2]._string = strings[node->parentEdge->stringIndex];
		cs[node->_c-2]._substring = NULL;
		cs[node->_c-2]._end = node->parentEdge->end;
	}

	g_slist_foreach(iter, node->edges) {
		Edge *edge = iter->data;
		int length = edge->end - edge->start + 1;
		findExactLongest(edge->child, cs, strings, depth+length);
	}
}

CommonString *find_lcstr(const gchar **strings) {
	return find_lcstr_callback(strings, nullCallback, NULL);
}

CommonString *find_lcstr_tree(const gchar **strings, SuffixTree *tree) {
	int K = pointerArrSize(strings);
	CommonString *cs = g_new0(CommonString, K-1);

	// compute C(v)
	int i;
	for (i = 0; i < K; i++) {
		countStringIndex(tree->root, i);
	}

	// count longest common substring in exactly k strings
	findExactLongest(tree->root, cs, strings, 0);

	// find longest common substring in at least k strings
	for (i = K-3; i >= 0; i--) {
		if (cs[i].length < cs[i+1].length) {
			cs[i] = cs[i+1];
		}
	}

	return cs;
}

char *cs_get_substring(CommonString *cs) {
	if (cs->_substring == NULL) {
		if (cs->length > 0) {
			cs->_substring = utf8_substring(cs->_string,
					cs->_end - cs->length + 1, cs->_end);
		}
	}
	return cs->_substring;
}

CommonString *find_lcstr_callback(const gchar **strings, TreeConstructionCallback callback, gpointer userData) {
	SuffixTree *tree = t_new_callback(strings, callback, userData);
	return find_lcstr_tree(strings, tree);
}

void cs_free(CommonString *cs, int K) {
	int i;
	for (i = 0; i < K-1; i++) {
		if (cs[i]._substring != NULL) {
			g_free(cs[i]._substring);
		}
	}
	g_free(cs);
}
